package java_core.two_array;

import java.util.Arrays;

/*561. 数组拆分 I https://leetcode-cn.com/problems/array-partition-i/solution/shu-zu-chai-fen-i-by-leetcode/
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
示例 1:
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:
n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].*/
public class ShuZuChaiFen {
/*
    从小到大排序，连续的两个数两两组合，就能保证1 到 n 的 min(ai, bi) 总和最大
    同理， 1 到 n 的 min(ai, bi) 总和最小， 则是相当于取升序数组的前半段数组
*/
    public int myArrayPairSum(int[] nums) {
        int sum = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                sum += nums[i];
            }
        }
        return sum;
    }

    public static void main(String[] args) {

    }


    public class Solution {
        int max_sum = Integer.MIN_VALUE;

        public int arrayPairSum(int[] nums) {
            permute(nums, 0);
            return max_sum;
        }

        public void permute(int[] nums, int l) {
            if (l == nums.length - 1) {
                int sum = 0;
                for (int i = 0; i < nums.length / 2; i++) {
                    sum += Math.min(nums[i], nums[nums.length / 2 + i]);
                }
                max_sum = Math.max(max_sum, sum);
            }
            for (int i = l; i < nums.length; i++) {
                swap(nums, i, l);
                permute(nums, l + 1);
                swap(nums, i, l);
            }
        }

        public void swap(int[] nums, int x, int y) {
            int temp = nums[x];
            nums[x] = nums[y];
            nums[y] = temp;
        }
    }

    public class Solution2 {
        public int arrayPairSum(int[] nums) {
            Arrays.sort(nums);
            int sum = 0;
            for (int i = 0; i < nums.length; i += 2) {
                sum += nums[i];
            }
            return sum;
        }
    }

    public class Solution3 {
        public int arrayPairSum(int[] nums) {
            int[] arr = new int[20001];
            int lim = 10000;
            for (int num : nums)
                arr[num + lim]++;
            int d = 0, sum = 0;
            for (int i = -10000; i <= 10000; i++) {
                sum += (arr[i + lim] + 1 - d) / 2 * i;
                d = (2 + arr[i + lim] - d) % 2;
            }
            return sum;
        }
    }


}
